#include "bigraph.h"
const double INF = 1000000000.0;

bool BiGraph::add_vertex(int v) {
	if (m_vertices.find(v) != m_vertices.end()) {
		return false;
	}
	m_vertices.insert(make_pair(v, new Vertex(v)));
	return true;
}

BiGraph::Edge* BiGraph::add_edge(int start, int end, double weight) {
	if (start == end) {
		return 0;
	}
	Vertex* start_vertex = find_or_create_vertex(start);
	Vertex* end_vertex = find_or_create_vertex(end);
	map <Vertex*, Edge*>::iterator existing_edge = start_vertex->m_out_edges.find(end_vertex);
	if (existing_edge != start_vertex->m_out_edges.end()) {
		return existing_edge->second;
	}
	Edge* new_edge = new Edge(start_vertex, end_vertex, weight);
	start_vertex->m_out_edges.insert(make_pair(end_vertex, new_edge));
	end_vertex->m_in_edges.insert(make_pair(start_vertex, new_edge));
	m_edges_count++;
	return new_edge;
}

BiGraph::Vertex* BiGraph::find_or_create_vertex(int v) {
	if (m_vertices.find(v) == m_vertices.end()) {
		Vertex* new_vertex = new Vertex(v);
		m_vertices.insert(make_pair(v, new_vertex));
		return new_vertex;
	}
	return m_vertices[v];

}

bool BiGraph::delete_edge (int start, int end) {
	if (m_vertices.find(start) == m_vertices.end() || m_vertices.find(end) == m_vertices.end())
		return false;
	map <Vertex*, Edge*>::iterator existing_edge = m_vertices[start]->m_out_edges.find(m_vertices[end]);
	if (existing_edge == m_vertices[start]->m_out_edges.end())
		return false;
	m_vertices[start]->m_out_edges.erase(m_vertices[end]);
	m_vertices[end]->m_in_edges.erase(m_vertices[start]);
	delete existing_edge->second;

	m_edges_count--;
	return true;

}

bool BiGraph::Ford_Bellman(int v, vector<double>& distances) {
     vector<int> parents;
     return Ford_Bellman(v, distances, parents);
}


bool BiGraph::Ford_Bellman(int v, vector<double>& distances, vector<int>& parents) {
    if (m_vertices.find(v) == m_vertices.end()) return false; //exception
    distances.resize(vertices_count(), INF);
    parents.resize(vertices_count());
    distances[v] = 0;
    
    bool there_were_changes = true;   
    for (int i = 0; i < vertices_count() && there_were_changes; i++) {
        there_were_changes = false;
        map <int, Vertex*>::iterator current_vertex = m_vertices.begin();
        while (current_vertex != m_vertices.end()) {
            map <Vertex*, Edge*>::iterator current_edge = current_vertex->second->m_out_edges.begin();
            while (current_edge != current_vertex->second->m_out_edges.end())
                if (distances[current_edge->second->end_vertex->name] > distances[current_vertex->second->name] + current_edge->second->weight) {
                    there_were_changes = true;
                    distances[current_edge->second->end_vertex->name] = distances[current_vertex->second->name] + current_edge->second->weight;        
                    parents[current_edge->second->end_vertex->name] = current_vertex->second->name;
                }
            current_vertex++;
        }
        if (i == vertices_count()-1 && there_were_changes) return false;
        if (i < vertices_count()-1 && !there_were_changes) return true;
    }  
}




int main() {
    return 0;
}

